{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6589ecd4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The greatest common divisor of 30 and 24 is 6\n"
     ]
    }
   ],
   "source": [
    "def euclidean_algorithm(a, b):\n",
    "    if a < b:\n",
    "        a, b = b, a\n",
    "    while b:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "# Example\n",
    "num1 = 30\n",
    "num2 = 24\n",
    "gcd_result = euclidean_algorithm(num1, num2)\n",
    "print(f'The greatest common divisor of {num1} and {num2} is {gcd_result}')\n",
    "# Output: The greatest common divisor of 30 and 24 is 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "15869652",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The discrete log of 17 base 13 modulo 31 is x = 17, since 13^17 % 31 = 17\n"
     ]
    }
   ],
   "source": [
    "def compute_dlp(g, a, p):\n",
    "    # exhaustive search for x: g^x = h (mod p)\n",
    "    current = 1\n",
    "    for x in range(p):\n",
    "        if current == a:\n",
    "            return x\n",
    "        current = (current * g) % p\n",
    "    return None  \n",
    "\n",
    "# example parameter\n",
    "g = 13  # generator\n",
    "a = 17  \n",
    "p = 31  # prime\n",
    "\n",
    "# 计算DLP\n",
    "x = compute_dlp(g, a, p)\n",
    "print(f\"The discrete log of {a} base {g} modulo {p} is x = {x}, since {g}^{x} % {p} = {a}\")\n",
    "\n",
    "# The discrete log of 17 base 13 modulo 31 is x = 14, since 13^14 % 31 = 17\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2ee68c57",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The DLP solution is valid.\n"
     ]
    }
   ],
   "source": [
    "def verify_dlp(g, x, a, p):\n",
    "    return pow(g, x, p) == a\n",
    "\n",
    "# verify DLP\n",
    "is_valid = verify_dlp(g, x, a, p)\n",
    "print(f\"The DLP solution is {'valid' if is_valid else 'invalid'}.\")\n",
    "\n",
    "# The DLP solution is valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cca9fdce",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
